Consistent Estimation of Mixed Memberships with Successive Projections

摘要

This paper considers the parameter estimation problem in Mixed MembershipStochastic Block Model (MMSB), which is a quite general instance of randomgraph model allowing for overlapping community structure. We present the newalgorithm successive projection overlapping clustering (SPOC) which combinesthe ideas of spectral clustering and geometric approach for separablenon-negative matrix factorization. The proposed algorithm is provablyconsistent under MMSB with general conditions on the parameters of the model.SPOC is also shown to perform well experimentally in comparison to otheralgorithms.